/**
 * 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
 * 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
 * 亚历克斯和李轮流进行，亚历克斯先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
 * 假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
 **/

/**
 * Solution 1:博弈论
 * 由于石子的堆数为偶数，且只能从两端取石子。因此先手后手所能选择的石子序列，完全取决于先手每一次决定。
 * 由于石子的堆数为偶数，对于先手而言：每一次的决策局面，都能「自由地」选择奇数还是偶数的序列，从而限制后手下一次「只能」奇数还是偶数石子。
 * 由于石子堆数为偶数，因此先手的最开始局面必然是 [奇数, 偶数][奇数,偶数]，即必然是「奇偶性不同的局面」；
 * 当先手决策完之后，交到给后手的要么是 [奇数,奇数][奇数,奇数] 或者 [偶数,偶数][偶数,偶数]，即必然是「奇偶性相同的局面」；
 * 后手决策完后，又恢复「奇偶性不同的局面」交回到先手 ...
 * 因此先手只需要在进行第一次操作前计算原序列中「奇数总和」和「偶数总和」哪个大，然后每一次决策都「限制」对方只能选择「最优奇偶性序列」的对立面即可。
 * 同时又由于所有石子总和为奇数，堆数为偶数，即没有平局，所以先手必胜。
 **/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

/**
 * Solution 2:动态规划
 * d[i][j]表示先手玩家和后手玩家在石子堆区间[i,j]之间轮流取石子，先手比后手多取的最大石子个数（最大差值）
 * 对于先手玩家，有两种拿法：
 * (1)拿开头的 piles[i]：先手玩家手里有了 piles[i]，因为在区间 [i + 1, j][i+1,j] 中只能由后手玩家来选择，
 * 则 dp[i + 1][j]表示的是后手玩家在这个区间内，比先手玩家多的最大石子个数，
 * 反过来 -dp[i + 1][j]表示在这个区间内，先手玩家比后手玩家多的最大石子个数；
 * (2)拿结尾的 piles[j]：先手玩家手里有了 piles[j]，因为在区间 [i, j - 1][i,j−1] 中只能由后手玩家来选择，
 * 则 dp[i][j - 1]dp表示的是后手玩家在这个区间内，比先手玩家多的最大石子个数，
 * 反过来 -dp[i][j - 1]表示在这个区间内，先手玩家比后手玩家多的最大石子个数；
 * 状态转移方程：dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1])
 * 当只有一个数时 dp[i][i]，此时先手玩家拿了必赢，所以 dp[i][i] = piles[i]
 **/
class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int len = piles.size();
        auto dp = vector<vector<int>>(len, vector<int>(len));

        // 当只有一个堆时
        for(int i=0; i<len; i++){
            dp[i][i] = piles[i];
        }

        for(int i=len-2; i>=0; i--){
            for(int j=i+1; j<len; j++){
                dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1]);
            }
        }
        return dp[0][len-1] > 0;
    }
};

int main(){
    vector<int> piles = {5,3,4,5};
    Solution s;
    bool result = s.stoneGame(piles);
    cout<<boolalpha<<result;
}